/**
 * 循环链表, 就是在单链表的基础上, 最后一个结点的指针域指向头结点(如果是有头结点的链表), 或者第一个元素结点(如果是没有头结点的链表)
 * 
 * 好处是, 在任意一个结点位置出发都可以找到链表中其他的元素, 而单链表的话则必须需要从头结点开始找
 * 
 * 使用循环链表时, 可以使用尾指针来方便操作: 
 * 例如, 将两个链表合并成一个表时, 仅需将第一个表的尾指针指向第二个表的第一个结点, 第二个表的尾指针指向第一个表的头结点, 然后释放第二个表的头结点
 * 
 */
#include <stdio.h>
#include <stdlib.h>

#include "./CircleLinkedList.h"

Status InitList(CircleLinkedList *list) {
    // 初始化头结点
    Node *headNode = (Node*)malloc(sizeof(Node));
    if(!headNode) {
        return ERROR;
    }

    // 头指针指向头结点
    *list = headNode;
    // 空表时, 头结点的指针域指向头结点
    headNode->next = headNode;

    return OK;
}

// 循环链表是否为空
int ListIsEmpty(CircleLinkedList list) {
    // 通过 头结点的指针域是否指向头结点 判断链表是否为空
    return list->next == list;
}

// 往链表中添加元素
Status AddElem(CircleLinkedList *list, ElemType e) {
    // 申请一个结点, 然后将结点的数据域放置为要添加的元素
    Node *nNode = (Node*)malloc(sizeof(Node));
    if(!nNode) {
        return ERROR;
    }
    nNode->data = e;

    // 新结点的指针域指向头结点
    nNode->next = (*list)->next;

    // 尾结点的指针域 指向 新结点
    (*list)->next = nNode;

    // 尾指针指向新添加的结点, 向后移动尾指针, 保证尾指针始终指向最后一个结点
    *list = nNode;
    return OK;
}

// 在指定位置 插入
// list为尾指针
Status InsertElem(CircleLinkedList *list, int index, ElemType e) {
    // 注意点, index最小是1, 最大是list的长度加一; 表示在第一个位置和最后一个位置

    // 位置不能小于1
    if(index < 1) {
        return ERROR;
    }
    
    // 要想在指定位置插入元素, 必须要先找到指定位置的前驱结点
    // 保存前驱结点
    // 找到头结点
    Node *curNode = (*list)->next;
    int curIdx = 0;

    // 因为是循环链表, 指针域不存在为NULL的情况, 所以需要判断 指针域不为尾结点
    // 合法位置为1至n+1, 
    // 这里来判断是否到尾指针了, 如果到了尾指针, 则说明到底了
    while(curIdx < index-1 && curNode != *list) {
        curNode = curNode->next;
        curIdx++;
    }

    // 如果查找到底了, 当前下标还是小于我想插入的位置, 则说明想要插入的位置过大
    if(curIdx < index-1) {
        return ERROR;
    }

    Node *np = (Node*)malloc(sizeof(Node));
    np->data = e;
    np->next = curNode->next;
    curNode->next = np;

    // 判断, 如果是在链表的结尾插入的元素, 则需要 向后移动尾指针
    if(curIdx == index-1 && curNode == *list) {
        *list = np;
    }

    return OK;
}

// 获取指定位置上的元素, 注意index是从1开始的, list是尾指针
Status GetElem(CircleLinkedList list, int index, ElemType *e) {
    if(index < 0) {
        return ERROR;
    }

    // 获取到首元结点(头结点的指针域)
    Node *curNode = list->next->next;
    // 首元结点的位置, 是第一个位置
    int curIdx = 1;

    // 当前位置不为index, 并且当前指针不是头结点
    while(curIdx < index && curNode != (list->next)) {
        curNode = curNode->next;
        curIdx++;
    }

    // 判断出错
    if(curIdx > index && curNode == list->next) {
        return ERROR;
    }

    *e = curNode->data;
    return OK;
}

// 置空链表
Status MakeEmpty(CircleLinkedList *list) {
    // 将首元结点 保存下来
    Node *curNode = (*list)->next->next;

    // 将链表置空
    // 1. 将尾指针 指向头结点; 当循环完成之后, curNode就是指向头结点
    *list = (*list)->next;
    // 2. 将头结点的指针域指向 自己
    (*list)->next = *list;

    // 即将要释放的结点
    Node *p = NULL;

    // 最后 从第一个结点开始释放掉所有结点
    // 循环条件是, 当前结点不是头结点时
    while(curNode != (*list)->next) {
        p = curNode;
        curNode = curNode->next;
        free(p);
    }

    return OK;
}

// 销毁链表
Status DestroyList(CircleLinkedList *list) {
    // 将首元结点 保存下来
    Node *curNode = (*list)->next;
    (*list)->next = NULL;

    Node *p = NULL;
    while(curNode) {
        p = curNode;
        curNode = curNode->next;
        free(p);
    }
    *list = NULL;
    return OK;
}

int main() {
    // 初始化
    CircleLinkedList list = NULL;
    InitList(&list);

    printf("isEmpty: %d\n", ListIsEmpty(list));

    // test AddElem
    // AddElem(&list, 1);
    // printf("isEmpty: %d\n", ListIsEmpty(list));

    // test InsertElem

    // 空元素时, 在第0个位置插入, 测试index<1
    // printf("%d\n", InsertElem(&list, 0, 23));

    // 测试超过最大插入位置
    printf("%d\n", InsertElem(&list, 1, 23));
    printf("%d\n", InsertElem(&list, 1, 25));
    printf("%d\n", InsertElem(&list, 3, 26));
    // error
    // printf("%d\n", InsertElem(&list, 4, 27));

    ElemType te;
    GetElem(list, 2, &te);
    printf("te = %d", te);

    MakeEmpty(&list);

    DestroyList(&list);

    return 0;
}
